package com.shujia.method_.eight;

/*

 */
public class MethodDemo2 {
    // 1, 1, 2, 3, 5, 8, 13
    // 前两项都是1, 从第三项开始每个数字都等于前两个数字的和
    // 计算第20个数字的值
    public static void main(String[] args) {
        System.out.println("非递归:" + fbDemo1(50));
        System.out.println("数组非递归:" + fbDemo2(50));
//         System.out.println("递归:" + fb(50));
    }

    // 递归
    public static int fb(int num) {
        if (num == 1 || num == 2) {
            return 1;
        }
        return fb(num - 1) + fb(num - 2);
    }

    public static int fbDemo2(int num) {
        int[] arr = new int[num];
        arr[0] = 1;
        arr[1] = 1;
        for (int i = 2; i < arr.length; i++) {
            arr[i] = arr[i - 1] + arr[i - 2];
        }
        return arr[arr.length - 1];
    }

    // 非递归的方式
    public static int fbDemo1(int num) {
        int first = 1;
        int second = 1;
        for (int i = 3; i <= num; i++) {
            int sum = first + second;
            first = second;
            second = sum;
        }
        return second;
    }


}
